package top.ivansong92.example.leetcode.learning.data.struct.array.sort;

/**
 * 归并排序
 */
public class MergeSort implements ArraySort {
    @Override
    public void sort(int[] array) {
        if (array == null || array.length < 2) {
            return;
        }
        int[] temp = new int[array.length];
        doSort(array, temp, 0, array.length - 1);

    }

    private void doSort(int[] array, int[] temp, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + (end - start) / 2;
        doSort(array, temp, start, mid);
        doSort(array, temp, mid + 1, end);
        mergeArray(array, temp, start, mid, end);
    }

    private void mergeArray(int[] array, int[] temp, int start, int mid, int end) {
        int left = start;
        int right = mid + 1;
        int index = 0;
        while (left <= mid && right <= end) {
            int leftVal = array[left];
            int rightVal = array[right];
            if (leftVal <= rightVal) {
                temp[index++] = leftVal;
                left++;
            } else {
                temp[index++] = rightVal;
                right++;
            }
        }

        while (left <= mid) {
            temp[index++] = array[left++];
        }

        while (right <= end) {
            temp[index++] = array[right++];
        }
        index = 0;
        for (int i = start; i <= end; i++) {
            array[i] = temp[index++];
        }
    }

}
